机器人塔
题目 机器人塔
思路分析
感觉是dp 但是状态表示什么的暂时没头绪
但是又有点像递推里的那个费解的开关
好像确定了一排后 其他的也确定了 所以能否枚举最底下一排的状态？
问题转变成了 二进制枚举底层情况 （从0~n） 然后根据底层情况做异或递推出上层情况
若最终满足 A、B个数满足 且推到了顶层 说明方案加1
up = (cur ^ (cur >> 1)) & ((1 << (clv - 1)) - 1)
如：cur=22（二进制位10110），clv为6
1、cur >> 1：将cur右移一位，右移一位为1011；
1 << (clv - 1）：1向左移动clv-1位，为01111
2、 (cur ^ (cur >> 1))：求上一层的情况，但最左边多出来一位
3、& ((1 << (clv - 1)) - 1)：和一个二进制位为01111相与（&）就能去掉最左边的一位。
注意“-”的优先级大于“>>”，所以需要加一个括号让<<先算。
抽丝剥茧下 发现和二进制有很大关系 所以 画模型很重要！
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
unordered_map<int,int> tier;
bool dfs(const bitset<32>& cur, int clv, int m, int n) {//cur:当前情况 clv:当前层数 m:A的剩余数量 n:B的剩余数量
if (m < 0 || n < 0)
return false;
if (clv == 0)
return m == 0 && n == 0;
int cb = cur.count();//计算这一层1的个数
int ca = clv - cb;//0就是当前层的数量减去1的数量 前导0无关
m -= ca;
n -= cb;
bitset<32> mask((1 << (clv - 1)) - 1);
bitset<32> up = (cur ^ (cur >> 1)) & mask; // 算出上一层的状态
return dfs(up, clv - 1, m, n);
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int A,B;
cin>>A>>B;
//M,N<500 最多1000人
for(int i=1;i*(i+1)<2000;i++){
tier[i*(i+1)/2]=i;
}
int level=tier[A+B];
int res=0;
for(int i=0;i<(1<<level);i++){
if (dfs(bitset<32>(i), level, A, B)) {
res++;
}
}
cout<<res<<endl;
return 0;
}
💬 评论